#include <bits/stdc++.h>
using namespace std;

/*
3318. 计算子数组的 x-sum I
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。

数组的 x-sum 计算按照以下步骤进行：

统计数组中所有元素的出现次数。
仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。
计算结果数组的和。
注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。

返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。

子数组 是数组内的一个连续 非空 的元素序列。

 

示例 1：

输入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

输出：[6,10,12]

解释：

对于子数组 [1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。
对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。
示例 2：

输入：nums = [3,8,7,8,7,5], k = 2, x = 2

输出：[11,15,15,15,12]

解释：

由于 k == x，answer[i] 等于子数组 nums[i..i + k - 1] 的总和。

 

提示：

1 <= n == nums.length <= 50
1 <= nums[i] <= 50
1 <= x <= k <= nums.length
*/

// 法一
class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> ans;
        // foreach len = k subArr
        for (int i = 0; i <= n - k; i++) {
            unordered_map<int, int> freq;
            // cur fac
            for (int j = i; j < i + k; j++) freq[nums[j]]++;

            // fac<-->dir vec map映射
            vector<pair<int, int>> tmp(freq.begin(), freq.end());
            sort(tmp.begin(), tmp.end(), [](const auto& a, const auto& b) {
                if (a.second != b.second)   return a.second > b.second;
                return a.first > b.first;
            });

            // calculate sum - x
            int sum = 0, take = min(x, (int)tmp.size());
            for (int k = 0; k < take; k++)  {
                sum += tmp[k].first * tmp[k].second;
            }
            ans.push_back(sum);
        }
        return ans;
    }
};

// 法二
class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        vector<vector<int>> ans;
        vector<int> answer;
        // 提取所有长度为k的连续子数组（滑动窗口）
        for(int i=0; i < nums.size()-k+1; i++){
            ans.emplace_back(nums.begin()+i, nums.begin()+i+k);
        }
        int ha[51] = {0}; // 频率统计数组（元素值范围0-50，数组效率高于哈希表）
        for(auto& win : ans){
            // 统计当前窗口各元素出现次数
            for(int i=0; i< k; i++){
                ha[win[i]]++;
            }
            int max_freq = 0;
            int temp_sum = 0;
            int selected = 0;
            // 选前x个符合条件的元素（频率降序，同频值大优先）
            while(selected++ < x){
                int selected_val = 0;
                // 从大到小遍历，保证同频时优先选大值
                for(int i = 50; i >= 0; i-- ){
                    if(ha[i] > max_freq){
                        max_freq = ha[i];
                        selected_val = i;
                    }
                }
                temp_sum += selected_val * max_freq; // 累加元素总贡献（值×出现次数）
                ha[selected_val] = -1; // 标记已选中，避免重复选择
                max_freq = 0; // 重置最大频率，找下一个目标
            }
            answer.push_back(temp_sum);
            // 重置频率数组，准备处理下一个窗口
            fill(ha, ha+51, 0);
        }
        return answer;
    }
};